﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Problems.Sorting;
using System.Linq;
using Algoritmia.Utils;

namespace Algoritmia.Problems.OrderStatistics
{
    public class MedianOf5Selector<T> : ISelector<T>
    {
        private readonly int _threshold;
        private readonly Func<IEnumerable<T>,DataStructures.Lists.IList<T>> _createList;
        private readonly Comparison<T> _comparison;
        private readonly ISorter<T> _sorter;

        public MedianOf5Selector(int threshold = 10, Comparison<T> comparison = null, Func<ISorter<T>> createSorter = null,
                                 Func<IEnumerable<T>,DataStructures.Lists.IList<T>> createList = null)
        {
            _threshold = threshold;
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            createSorter = createSorter ?? (() => new BasicQuickSorter<T>());
            _sorter = createSorter();
            _createList = createList ?? (it => AlgoritmiaFactory.Lists<T>.BuildDefault(it));
        }

        private static void Swap(ref T a, ref T b)
        {
            T aux = b;
            b = a;
            a = aux;
        }

        private T MedianOf5(DataStructures.Lists.IList<T> list, int i)
        {
            T u = list[i], v = list[i + 1], w = list[i + 2], x = list[i + 3];

            if ( _comparison(v,u) > 0)
            {
                Swap(ref u, ref v);
            }
            if ( _comparison(x,w) > 0)
            {
                Swap(ref x,ref w);
            }
            if ( _comparison(u,w) < 0)
            {
                u = list[i + 4];
                if ( _comparison(v,u) > 0)
                {
                    Swap(ref u,ref v);
                }
            }
            else
            {
                w = list[i + 4];
                if ( _comparison(w,x) > 0)
                {
                    Swap(ref w, ref x);
                }
            }

            if ( _comparison(u,w) < 0)
            {
                return _comparison(v, w) < 0? v : w;
            }
            else
            {
                return _comparison(x, u) < 0 ? x : u;
            }
           
        }

        #region Implementation of ISelector<T>

        public T Select(DataStructures.Lists.IList<T> list, int k)
        {
            if (k <= 0 && k >= list.Count)
                throw new ArgumentOutOfRangeException("k");

            if ( list.Count <= _threshold)
            {
                return _sorter.Sorted(list).ElementAt(k);
            }
            else
            {
                var m = _createList(Enumerable.Empty<T>());
                for(int i = 0; i <= list.Count-5; i += 5)
                {
                    m.Add(MedianOf5(list, i));
                }
                T pivot = Select(m, m.Count/2);
                int lessthan = 0, equal = 0;
                foreach(var v in list)
                {
                    if (_comparison(v, pivot) < 0) lessthan++;
                    if (_comparison(v, pivot) == 0) equal++;
                }
                if ( k < lessthan)
                {
                    return Select(_createList(list.Where(e => _comparison(e, pivot) < 0)),k);
                }
                if ( k >= lessthan+equal)
                {
                    return Select(_createList(list.Where(e => _comparison(e, pivot) > 0)), k-lessthan-equal);
                }
                return pivot;
            }
        }

        #endregion
    }
}
